1. Field of the Invention
The present invention relates to cryptographic algorithms and, in particular, to division algorithms suitable for cryptographic applications.
2. Description of the Related Art
The division of two long numbers is often required in cryptographic algorithms. In the RSA algorithm, for example, the modulus N is a product of two prime numbers p, q, wherein q is obtained when N is divided by p, or p is obtained when N is divided by q.
If a division routine is not incorporated on a cryptographic coprocessor used for this as an explicit command consisting of micro-commands which are internally processed quickly, the division must take place by means of software. Conventional division routines for this are slow on the one hand and not safe against SPA attacks (SPA=Simple Power Analysis) on the other hand.
Usual division routines, as are, for example, described in “Computer Arithmetic”, Henessy and Patterson, Morgan Kaufmann Publishers, Inc., 1996, such as, e.g., the restoring division, the non-restoring division etc., are based on register shifts taking place and subtractions or additions being performed, depending on whether certain bits have certain values. Routines of this kind are susceptible to SPA attacks since the current or power consumption and, additionally, the time consumption depend on the numbers to be processed. An attacker could thus draw conclusions as to the numbers processed from the current or time profile and thus for example spy out a secret key of a public-key crypto algorithm.
In order to tackle this problem, so-called dummy operations by which a homogenization of the current profile can be obtained are incorporated. The incorporation of dummy operations, however, results in an additional performance loss which can amount to 33%.